|
In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987. The name of Fibonacci heap comes from Fibonacci numbers which are used in the running time analysis. Find-minimum is ''O''(1) amortized time.〔 Third edition p. 518.〕 Operations insert, decrease key, and merge (union) work in constant amortized time.〔 Operations delete and delete minimum work in ''O''(log ''n'') amortized time.〔 This means that starting from an empty data structure, any sequence of ''a'' operations from the first group and ''b'' operations from the second group would take ''O''(''a'' + ''b'' log ''n'') time. In a binomial heap such a sequence of operations would take ''O''((''a'' + ''b'') log ''n'') time. A Fibonacci heap is thus better than a binomial heap when ''b'' is asymptotically smaller than ''a''. Using Fibonacci heaps for priority queues improves the asymptotic running time of important algorithms, such as Dijkstra's algorithm for computing the shortest path between two nodes in a graph. == Structure == A Fibonacci heap is a collection of trees satisfying the minimum-heap property, that is, the key of a child is always greater than or equal to the key of the parent. This implies that the minimum key is always at the root of one of the trees. Compared with binomial heaps, the structure of a Fibonacci heap is more flexible. The trees do not have a prescribed shape and in the extreme case the heap can have every element in a separate tree. This flexibility allows some operations to be executed in a "lazy" manner, postponing the work for later operations. For example, merging heaps is done simply by concatenating the two lists of trees, and operation ''decrease key'' sometimes cuts a node from its parent and forms a new tree. However at some point some order needs to be introduced to the heap to achieve the desired running time. In particular, degrees of nodes (here degree means the number of children) are kept quite low: every node has degree at most ''O''(log ''n'') and the size of a subtree rooted in a node of degree ''k'' is at least ''F''''k''+2, where ''Fk'' is the ''k''th Fibonacci number. This is achieved by the rule that we can cut at most one child of each non-root node. When a second child is cut, the node itself needs to be cut from its parent and becomes the root of a new tree (see Proof of degree bounds, below). The number of trees is decreased in the operation ''delete minimum'', where trees are linked together. As a result of a relaxed structure, some operations can take a long time while others are done very quickly. For the amortized running time analysis we use the potential method, in that we pretend that very fast operations take a little bit longer than they actually do. This additional time is then later combined and subtracted from the actual running time of slow operations. The amount of time saved for later use is measured at any given moment by a potential function. The potential of a Fibonacci heap is given by :Potential = ''t'' + 2''m'' where ''t'' is the number of trees in the Fibonacci heap, and ''m'' is the number of marked nodes. A node is marked if at least one of its children was cut since this node was made a child of another node (all roots are unmarked). The amortized time for an operation is given by the sum of the actual time and ''c'' times the difference in potential, where ''c'' is a constant (chosen to match the constant factors in the ''O'' notation for the actual time). Thus, the root of each tree in a heap has one unit of time stored. This unit of time can be used later to link this tree with another tree at amortized time 0. Also, each marked node has two units of time stored. One can be used to cut the node from its parent. If this happens, the node becomes a root and the second unit of time will remain stored in it as in any other root. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fibonacci heap」の詳細全文を読む スポンサード リンク
|